#include <iostream>

#include "trie.hpp"

bool trie::erase(const std::string& str) {
     bool found=false;
   
    if(this->m_size>0 ){
        if(str.size()==0){
            for(int i=1;i<=this->m_size;i++){
                if(this->m_root->children[i]->children[0]->payload=='0'){
                    found= true;
                    delete this->m_root->children[i]->children[0];
                    this->m_root->children[i]->children[0]=nullptr;
                    
                    //delete this->m_root->children[i]->parent;
                    this->m_root->children[i]->parent=nullptr;
                    
                    delete this->m_root->children[i];
                    this->m_root->children[i]=nullptr;
                   
                    for(int y=i;y<this->m_size;y++){
                        this->m_root->children[y]=this->m_root->children[y+1];
    
                    }
                    this->m_size--;
                    break;
                }
            
            }
        }
        else{
            for (int x=1; x<=this->m_size;x++){
                 int counter=0,y=0;
                                     

                while(this->m_root->children[x]->children[y]->is_terminal!=true){
                    counter++;
                    y++;
                }
                 counter++;
                 if(counter==str.size()){
                    for(int u=0;u<counter;u++){
                        if(str.at(u)==this->m_root->children[x]->children[u]->payload){
                            found=true;
                        }else{
                            found=false;
                            break;
                        }
                    
                    }
                    if(found==true){
                        for(int m=0;m<str.size();m++){
                            delete this->m_root->children[x]->children[m];
                            //delete this->m_root->children[x]->parent;
                            this->m_root->children[x]->children[m]=nullptr;
                            this->m_root->children[x]->parent=nullptr;
                            
                        
                        }
                        delete this->m_root->children[x];
                        this->m_root->children[x]=nullptr;
                       
                         for(int m=x;m<this->m_size;m++){
                            this->m_root->children[m]=this->m_root->children[m+1];
    
                         }
                        this->m_size--;
                        return true;
                        
                    }
                 
                 
                 }
            
            
            }
        
        }
    }
    return found;

}

bool trie::insert(const std::string& str) {
   
     
   
     if(! contains(str)){
        if(str.length()==0){
             m_size++;
             m_root->children[ m_size]=new trie_node;
             m_root->children[ m_size]->payload='1'; 
             m_root->children[ m_size]->is_terminal=true; 
             m_root->children[m_size]->parent=m_root;
             
             if(m_size>1){m_root->children[ m_size-1]->is_terminal=false;} 

             m_root->children[ m_size]->children[0]= new trie_node;
             m_root->children[ m_size]->children[0]->payload='0';
             m_root->children[ m_size]->children[0]->is_terminal=true;
             m_root->children[ m_size]->children[0]->parent= m_root->children[ m_size];

        }else{
             m_size++;
             m_root->children[ m_size]=new trie_node;
             m_root->children[ m_size]->payload='1';
             m_root->children[ m_size]->is_terminal=true; 
                          m_root->children[m_size]->parent=m_root;

             if(m_size>1){m_root->children[ m_size-1]->is_terminal=false;} 

            for(int i=0;i<str.length();i++){
                 m_root->children[ m_size]->children[i]= new trie_node;
                 m_root->children[ m_size]->children[i]->payload=str.at(i);
                 m_root->children[ m_size]->children[i]->parent=   m_root->children[ m_size];

            if(i==str.length()-1){
                   m_root->children[this->m_size]->children[i]->is_terminal=true;
               }
        }}
        return true;
    }
    
    
    return false;
}

bool trie::contains(const std::string& str) const {
   
     bool found=false;
   
    if(this->m_size>0 ){
        if(str.size()==0){
            for(int i=1;i<=this->m_size;i++){
                if(this->m_root->children[i]->children[0]->payload=='0'){
                    found= true;
                    break;
                }
            
            }
        }
        else{
            for (int x=1; x<=this->m_size;x++){
                 int counter=0,y=0;
                                     

                while(this->m_root->children[x]->children[y]->is_terminal!=true){
                    counter++;
                    y++;
                }
                 counter++;
                 if(counter==str.size()){
                    for(int u=0;u<counter;u++){
                        if(str.at(u)==this->m_root->children[x]->children[u]->payload){
                            found=true;
                        }else{
                            found=false;
                            break;
                        }
                    
                    }
                    if(found==true){
                        return true;
                        
                    }
                 
                 
                 }
            
            
            }
        
        }
    }
    return found;
}

trie::trie(){
  delete m_root;
   m_root=new trie_node;
    m_size= 0;
   m_root->is_terminal=false;
   m_root->payload='0';
}

trie::trie(const std::vector<std::string>& strings) {
   this->m_root=new trie_node;
    
   this->m_root->is_terminal=false;
   this->m_root->payload='0';

 for (int i=0; i<strings.size();i++) {
        insert(strings.at(i));
    }
}

trie::trie(const trie& rhs) {
    
    const_iterator iteratorB=rhs.begin();
    std::vector<std::string> constructorString(rhs.m_size);
    int i=0;
    while(iteratorB!=nullptr){
        constructorString[i]=*iteratorB;
        i++;
        iteratorB++;
    }
    
    m_root=new trie_node;
    m_root->is_terminal=rhs.m_root->is_terminal;
    m_root->parent=rhs.m_root->parent;
    m_size=0;
    for(int y=0;y<constructorString.size();y++){
        insert(constructorString[y]);
    
    
    }
    

}

trie& trie::operator=(const trie& rhs) {
    if(*this==rhs){
        return *this;
    }
    for(int i=0;i<=m_size;i++){
     
         int x=0;
         if(m_root->children[i]!=nullptr){
                  while(m_root->children[i]->children[x]->is_terminal!=true){
                      
                      m_root->children[i]->children[x]->parent=nullptr;
                      delete m_root->children[i]->children[x];
                      m_root->children[i]->children[x]=nullptr;
                      
                      
                      x++;  
                  }
                  
                  m_root->children[i]->children[x]->parent=nullptr;
                  delete m_root->children[i]->children[x];
                  m_root->children[i]->children[x]=nullptr;
                    }
                  delete m_root->children[i];
                  m_root->children[i]=nullptr;
    
    }
   delete m_root;
   m_root=nullptr;
   m_size=0;
   
    const_iterator iteratorB=rhs.begin();
    std::vector<std::string> constructorString(rhs.m_size);
    int i=0;
    while(iteratorB!=nullptr){
        constructorString[i]=*iteratorB;
        i++;
        iteratorB++;
    }
    
    m_root=new trie_node;
    m_root->is_terminal=rhs.m_root->is_terminal;
    m_root->parent=rhs.m_root->parent;
    for(int y=0;y<constructorString.size();y++){
        insert(constructorString[y]);
    
    
    }
    
    return *this;
}

trie::trie(trie&& rhs) {
    
    m_root=new trie_node;
    
    for(int i=1;i<=rhs.m_size;i++){
        m_root->children[i]=rhs.m_root->children[i];
        //rhs.m_root->children[i]=nullptr;
        m_root->children[i]->parent=m_root;
    }
   
    
    //rhs.m_root=nullptr;
    m_size=rhs.m_size;
    rhs.m_size=0;

}

trie& trie::operator=(trie&& rhs) {
   for(int i=0;i<=m_size;i++){
     
         int x=0;
         if(m_root->children[i]!=nullptr){
                  while(m_root->children[i]->children[x]->is_terminal!=true){
                      
                      m_root->children[i]->children[x]->parent=nullptr;
                      delete m_root->children[i]->children[x];
                      m_root->children[i]->children[x]=nullptr;
                      
                      
                      x++;  
                  }
                  
                  m_root->children[i]->children[x]->parent=nullptr;
                  delete m_root->children[i]->children[x];
                  m_root->children[i]->children[x]=nullptr;
                    }
                  delete m_root->children[i];
                  m_root->children[i]=nullptr;
    
    }
   delete m_root;
   m_root=nullptr;
   m_size=0;
    m_root=new trie_node;
    
    for(int i=1;i<=rhs.m_size;i++){
        m_root->children[i]=rhs.m_root->children[i];
        //rhs.m_root->children[i]=nullptr;
          m_root->children[i]->parent=m_root;
    }
   
    
    //rhs.m_root=nullptr;
    m_size=rhs.m_size;
    rhs.m_size=0;

    return *this;
}



trie::~trie() {
for(int i=0;i<=m_size;i++){
     
         int x=0;
         if(m_root->children[i]!=nullptr){
                  while(m_root->children[i]->children[x]->is_terminal!=true){
                      
                      m_root->children[i]->children[x]->parent=nullptr;
                      delete m_root->children[i]->children[x];
                      m_root->children[i]->children[x]=nullptr;
                      
                      
                      x++;  
                  }
                  
                  m_root->children[i]->children[x]->parent=nullptr;
                  delete m_root->children[i]->children[x];
                  m_root->children[i]->children[x]=nullptr;
                    }
                  delete m_root->children[i];
                  m_root->children[i]=nullptr;
    
    }
   delete m_root;
   m_root=nullptr;
   m_size=0;
   


}

size_t trie::size() const {
    return this->m_size;
}

bool trie::empty() const {
    return m_size==0;
}

std::vector<std::string> trie::search_by_prefix(const std::string& str) const {
      const_iterator iteratorB=begin(),iteratorE=end();
    std::vector<std::string> returnVector;
    returnVector.reserve(m_size);

    std::string readString;
    int y=0;
    bool matches=true;
    
    while (iteratorB!=iteratorE) {
        
        readString=*iteratorB;
        if(readString.length()>=str.length()){
            for(int i=0;i<str.length();i++){
                if(readString.at(i)!=str.at(i)){
                    matches=false;
                    break;
                }
            
            }
            if(matches){
                returnVector.push_back(readString);
                y++;
            }
        
        
        }
        matches=true;
        iteratorB++;
    }

 return returnVector;
}

std::vector<std::string> trie::get_prefixes(const std::string & str) const {
       const_iterator iteratorB=begin(),iteratorE=end();
    std::vector<std::string> returnVector;
    returnVector.reserve(m_size);
    std::string readString;
    int y=0;
    
    bool matches=true;
    
    while (iteratorB!=iteratorE) {
       
        readString=*iteratorB;
        if(readString.length()<=str.length()){
            for(int i=0;i<readString.length();i++){
                if(readString.at(i)!=str.at(i)){
                    matches=false;
                    break;
                }
            
            }
            if(matches){
                returnVector.push_back(readString);
                y++;
            }
        
        
        }
        matches=true;
        iteratorB++;
    }

 return returnVector; 
}

trie::const_iterator trie::begin() const {
    if(m_size>0){
    return const_iterator(this->m_root->children[1]);}else{
        return nullptr;
    }
    
}

trie::const_iterator trie::end() const {
    return const_iterator(nullptr);
}

void trie::swap(trie& rhs) {
    trie_node* a =rhs.m_root;
    rhs.m_root=this->m_root;
    this->m_root=a;
    int i ;
    i= m_size;
    m_size=rhs.m_size;
    rhs.m_size=i;
}

bool trie::operator==(const trie& rhs) const {
    const_iterator iteratorBegin= begin(),iteratorEnd=end();
    if(m_size!=rhs.m_size){return false;}
    while (iteratorBegin!=iteratorEnd) {
        if(!rhs.contains(iteratorBegin.operator *())){
            return false;
        }
        iteratorBegin++;
        
    }

    
   return true; 
}

bool trie::operator<(const trie& rhs) const {
    if (m_size<rhs.m_size) {
        return true;

    }
    if(m_size>rhs.m_size){
        return false;
    }
    const_iterator thisIteratorB,thisIteratorE,rhsIteratorB,rhsIteratorE;
    int i=0,y=0;
    std::string temp;
    thisIteratorB=begin();
    thisIteratorE=end();
    rhsIteratorB=rhs.begin();
    rhsIteratorE=rhs.end();
    
    
    std::vector<std::string> thisString(m_size),rhsString(rhs.size());
    
    while (thisIteratorB!=thisIteratorE) {
        thisString[i]=*thisIteratorB;
        i++;
        thisIteratorB++;
    }
    while(rhsIteratorB!=rhsIteratorE){
        rhsString[y]=*rhsIteratorB;
        y++;
        rhsIteratorB++;
    }
    for(int x=0; x< m_size-1;x++){
        for(int m=x+1;m<m_size;m++){
            if(thisString[x]>thisString[m]){
                temp=thisString[x];
                thisString[x]=thisString[m];
                thisString[m]=temp;
            
            }
            if(rhsString[x]>rhsString[m]){
                temp=rhsString[x];
                rhsString[x]=rhsString[m];
                rhsString[m]=temp;
            
            }
        
        }
    
    }
    for(int l=0; l< m_size;l++){
        if(thisString[l]>rhsString[l]){
            return false;
        }
    
    }
    
    
    return true;
}

trie trie::operator&(trie const& rhs) const {
    trie returnTrie ;
    const_iterator thisIteratorB,thisIteratorE,rhsIteratorB,rhsIteratorE;
    std::vector<std::string> constructString;
    constructString.reserve((rhs.m_size+m_size));
    thisIteratorB=begin();
    thisIteratorE=end();
    int i=0;
    while(thisIteratorB!=thisIteratorE){
        if(rhs.contains(*thisIteratorB)){
            constructString.push_back(*thisIteratorB);
            i++;
        }
        thisIteratorB++;
    }
    returnTrie=trie(constructString);
    
    return returnTrie;
}

trie trie::operator|(trie const& rhs) const {
    trie returnTrie ;
   
           
    const_iterator thisIteratorB,thisIteratorE,rhsIteratorB,rhsIteratorE;
    std::vector<std::string> constructString;
    constructString.reserve((rhs.m_size+m_size));
    thisIteratorB=begin();
    thisIteratorE=end();
    rhsIteratorB=rhs.begin();
    rhsIteratorE=rhs.end();
    int i=0;
    while(thisIteratorB!=thisIteratorE){
        
            constructString.push_back(*thisIteratorB);
            i++;
            ++thisIteratorB;
        
    
    }
    while (rhsIteratorB!=rhsIteratorE) {
        if(!contains(*rhsIteratorB)){
            constructString.push_back(*rhsIteratorB);
            i++;
        }
        ++rhsIteratorB;
    }

    returnTrie=trie(constructString);
    
    return returnTrie;
}

bool operator!=(const trie& lhs, const trie& rhs) {
	return !(lhs == rhs);
}

bool operator>(const trie& lhs, const trie& rhs) {
	return rhs < lhs;
}

bool operator<=(const trie& lhs, const trie& rhs) {
	return !(lhs > rhs);
}

bool operator>=(const trie& lhs, const trie& rhs) {
	return !(lhs < rhs);
}

void swap(trie& lhs, trie& rhs) {
    lhs.swap(rhs);
}

std::ostream& operator<<(std::ostream& out, trie const& trie) {
    return out;
}

trie::const_iterator& trie::const_iterator::operator++() {
    
    
     bool match=true;
    int i=0,x=0;
    if(current_node==nullptr){return *this;}
    if(current_node->is_terminal){
        current_node=nullptr;
        return *this;
    }
    do{
        i++;
        match=true;
        while(!current_node->children[x]->is_terminal)
        {
           
            if(current_node->parent->children[i]->children[x]->is_terminal){
                match=false;
                 
                break;
            }
            if((current_node->parent->children[i]->children[x])!=current_node->children[x]){
                match=false;
                
                break;
            }
            
            x++;
        
        }
        
        if(!current_node->parent->children[i]->children[x]->is_terminal){
                match=false;
                
                
            }
            if((current_node->parent->children[i]->children[x])!=current_node->children[x]){
                match=false;
                
            }
        
        if(match){
            current_node=current_node->parent->children[i+1];
            
            break;
        }
      
                   
    }
    while (!current_node->parent->children[i]->is_terminal) ;
  
    

    
    
    return *this;
}

trie::const_iterator trie::const_iterator::operator++(int) {
    trie::const_iterator copy(*this);
    ++(*this);
    
    return copy;
}

trie::const_iterator::const_iterator(const trie_node* node) {
    current_node=node   ;
 
}

bool trie::const_iterator::operator==(const trie::const_iterator& rhs) const {
    return current_node==rhs.current_node;
}

bool trie::const_iterator::operator!=(const trie::const_iterator& rhs) const {
    return !(*this==rhs);
}

trie::const_iterator::reference trie::const_iterator::operator*() const {
    std::string returnString="";
    int i=0;
    if (current_node->children[0]->is_terminal&&current_node->children[0]->payload!='0') {
        returnString+=current_node->children[0]->payload;
        return returnString;

    }

    do{
         
        if((current_node->children[i]->payload=='0'&&i==0)){break;}
        returnString+=current_node->children[i]->payload;
       
       i++;
    }
    while(!current_node->children[i]->is_terminal);
    if(i!=0 ){returnString+=current_node->children[i]->payload;}
    return returnString;
}
